/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.graph
 * author:David
 * Date:2015年8月21日上午11:47:07
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.graph;

import com.xuwei.base.link.LinkedList;
import com.xuwei.base.link.LinkedListDLNode;
import com.xuwei.base.stack.Stack;
import com.xuwei.base.stack.StackSLinked;
import com.xuwei.ext.exception.UnsupportedOpertation;

/**
 * 有向图
 * @author David
 * @since 2015年8月21日 上午11:47:07
 * @version 
 * @since JDK 1.6
 */
public class DirectGraph extends AbstractGraph {

	@Override
	public void remove(Vertex v) {
		super.remove(v);
	}

	@Override
	public void remove(Edge e) {
		super.remove(e);
	}

	@Override
	public Edge edgeFromTo(Vertex u, Vertex v) {
		Edge edge = null;
		Iterator it = u.getAdjacentEdges().elements();
		for(it.first();!it.isDone();it.next()){
			Edge _edge = (Edge) it.currentItem();
			Vertex _vertex = (Vertex) _edge.getSecondVexPosition().getData();
			if(v==_vertex){
				edge = _edge;
				break;
			}
		}
		return edge;
	}

	@Override
	public Iterator adjVertexs(Vertex v) {
		LinkList list=v.getAdjacentEdges();
		Iterator it=list.elements();
		LinkList vlist=new LinkListDLNode();
		for(it.first();!it.isDone();it.next()){
			Edge e=(Edge)it.currentItem();
			Vertex u=(Vertex) e.getSecondVexPosition().getData();
			vlist.insertLast(u);		
		}
		Iterator iterator=new LinkListIterator(vlist);
		return iterator;
	}

	@Override
	public Iterator toplogicalSort() throws UnsupportedOpertation {
		LinkList topSeq = new LinkListDLNode();//拓扑序列
		Stack s = new StackSLinked();
		Iterator it = getVertex();
		for(it.first();!it.isDone();it.next()){//初始化顶点集应用信息
			Vertex v = (Vertex)it.currentItem();
			v.setAppObj(Integer.valueOf(v.getInDeg()));
			if(v.getInDeg()==0){
				s.push(v);
			}
		}
		while(!s.isEmpty()){
			Vertex v = (Vertex)s.pop();
			topSeq.insertLast(v);  //生成拓扑序列
			Iterator adjIt = adjVertexs(v); //对于v的每个邻接点入度减1
			for(adjIt.first();!adjIt.isDone();adjIt.next()){
				Vertex adjV = (Vertex)adjIt.currentItem();
				int in = getTopInDev(adjV)-1;
				setTopInDe(adjV, in);
				if(in==0){
					s.push(adjV);//入度为0的顶点入栈
				}
			}//for adjIt
		}//while
		if(topSeq.getSize()<getVexNum()){
			return null;
		}else{
			return topSeq.elements();
		}
	
	}

	@Override
	public void criticalPath() throws UnsupportedOpertation {
		Iterator it = toplogicalSort();
		resetEdgeType();  //重置图中各边的类型信息
		if(it==null){
			return;
		}
		LinkList reTopSeq = new LinkListDLNode();//逆拓扑序列
		for(it.first();!it.isDone();it.next()){//初始化各点ve与vl，并生成逆拓扑序列
			Vertex v = (Vertex)it.currentItem();
			Vtime time = new Vtime(0, Integer.MAX_VALUE);//ve=0, vl=无穷大
			v.setAppObj(time);
			reTopSeq.insertFirst(v);
		}
		for(it.first();!it.isDone();it.next()){//正向拓扑序列求各点ve
			Vertex v = (Vertex)it.currentItem();
			Iterator adjIt = adjVertexs(v);
			for(adjIt.first();!adjIt.isDone();adjIt.next()){
				Vertex adjV = (Vertex)adjIt.currentItem();
				Edge e = edgeFromTo(v, adjV);
				if(getVE(v)+e.getWeight()>getVE(adjV)){//更新最早开始时间
					setVE(adjV, getVE(v)+e.getWeight());
				}
			}
		}
		Vertex dest = (Vertex)reTopSeq.first().getData();
		setVL(dest, getVE(dest));    //设置汇点 vl=ve
		Iterator reIt = reTopSeq.elements();
		for(reIt.first();!reIt.isDone();reIt.next()){//逆拓扑序列求各点vl
			Vertex v = (Vertex)reIt.currentItem();
			Iterator adjIt = adjVertexs(v);
			for(adjIt.first();!adjIt.isDone();adjIt.next()){
				Vertex adjV = (Vertex)adjIt.currentItem();
				Edge e = edgeFromTo(v, adjV);
				if(getVL(v)>getVL(adjV)-e.getWeight()){//更新最迟开始时间
					setVL(v, getVL(adjV)-e.getWeight());
				}
			}
		}
		Iterator edIt = getEdge();
		for(edIt.first();!edIt.isDone();edIt.next()){
			Edge e = (Edge)edIt.currentItem();
			Vertex u = e.getFirstVex();
			Vertex v = e.getSecondVex();
			if(getVE(u)==getVL(v)-e.getWeight()){
				e.setToCritical();
			}
		}
		
	}
	
	/**
	 * @param v
	 * @return
	 */
	private int getVL(Vertex v) {
		return ((Vtime)v.getAppObj()).getVl();
	}

	/**
	 * @param dest
	 * @param ve
	 */
	private void setVL(Vertex v, int vl) {
		((Vtime)v.getAppObj()).setVl(vl);
	}

	/**
	 * @param adjV
	 * @param i
	 */
	private void setVE(Vertex v, int ve) {
		((Vtime)v.getAppObj()).setVe(ve);
	}

	/**
	 * @param v
	 * @return
	 */
	private int getVE(Vertex v) {
		return ((Vtime)v.getAppObj()).getVe();
	}

	@Override
	public int getType() {
		return 1;//有向图返回1
	}
	
	//取顶点v的当前入度
	private int getTopInDev(Vertex v){
		return ((Integer)v.getAppObj()).intValue();
	}

	//设置顶点v的当前入度
	private void setTopInDe(Vertex v, int indegree){
		v.setAppObj(Integer.valueOf(indegree));
	}

}
